\section{Preliminaries} \label{sec:prelim}


\subsection{Security Model}

Our protocols are presented in the semi-honest three-party setting with an honest majority. That is, the received messages of any single party are computationally indistinguishable from messages that are only dependent of their final output. We present our ideal functionality in \figureref{fig:full_ideal}. See \cite{highthroughput} for a more details of our simulation based security model. 


\iffullversion
Throughout the exposition we will assume these three parties, which we sometimes call \emph{servers}, provide the sets which are computed on. However, in the general case the sets being computed on can be privately input by an arbitrary party which does not participate in the computation. These \emph{client} parties will secret share their set between the servers and reconstruct the output shares that are intended for them. This setting is often referred to as the client server model\cite{aby3, secureML}. Later on we will also consider a setting with five servers that can tolerate the adversary corrupting any two of them. However, we will explicitly state when this alternative model is being considered.
\fi


\subsection{Notation}




Let $[m]$ denote the set $\{1,2,...,m\}$. Let $V$ be a vector with elements $V=(V_1,...,V_n)$. We also use the notion $V[i]$ to index the $i$th element $V_i$.
We define a permutation of size $m$ as an injective function $\pi : [m] \rightarrow [m]$. We extend this definition such that when $\pi$ is applied to a vector $V$ of $m$ elements, then  $\pi(V)=(V_{\pi(1)}, ..., V_{\pi(m)})$. The image of a function $f : X \rightarrow Y$ is defined as $image(f) := \{y\in Y : \exists x\in X, f(x)=y\}$. Preimage of a pair $(f,y)$ is defined as $preimage(f,y):=\{x\in X : f(x) = y\}$. We use $n$ to represent the number of rows a table has. Parties are referred to as $P_0,P_1,P_{2}$. We use $\kappa$ to denote the computational security parameter, e.g. $\kappa =128$, and $\lambda$ as the statistical security parameters, e.g. $\lambda=40$.

\subsection{Secret Sharing Framework}
Our protocol builds on the ABY$^3$ framework of Rindal and Mohassel~\cite{aby3} for secure computation of circuits. That is, we use their binary/arithmetic addition and multiplication protocols along with their share conversion protocols. We will use the notation that $\share{x}$ is a 2-out-of-3 \emph{binary replicated secret sharing} of the value $x$. That is, $(x_0,x_1,x_2)$ are sampled uniformly s.t. $x=x_0\oplus x_1\oplus x_2$. Party \Party{i} holds the shares $x_i, x_{i+1\mod 3}$. We use the notation $\share{x}_i$ to refer to share $x_i$.  \share{x} can locally be converted to a 2-out-of-2 sharing \shareTwo{x} where \Party{i} holds $x_0'$ and \Party{j} holds $x_1'$ s.t. $x=x_0'\oplus x_1'$, e.g. $i=0,j=1$. $\shareTwo{x}_k$ refers to $x_k'$. \shareTwo{x} can also be converted back to $\share{x}$ using one round of communication. 


\iffullversion
 Note that the framework of \cite{aby3} provides efficient facilities to convert between different types of shares, e.g. binary, arithmetic and fixed point.
\fi

\subsection{Cuckoo Hash Tables}

The core data structure that our protocols employ is a cuckoo hash table which is parameterized by a capacity $n$, two (or more) hash functions $h_0, h_1$ and a vector $T$ which has $m=O(n)$ slots, $T[1], ..., T[m]$. For any $x$ that has been added to the hash table, there is an invariant that $x$ will be located at $T[{h_0(x)}]$ or $T[{h_1(x)}]$. Testing if an $x$ is in the hash table therefore only requires inspecting these two locations. $x$ is added to the hash table by inserting $x$ into slot $T[h_i(x)]$ where $i\in \{0,1\}$ is picked at random. If there is an existing item at this slot, the old item $y$ is removed and reinserted at its other hash function location. 
\iffullversion
Given a hash table with $m\approx1.6n$ slots and three hash functions, then with overwhelming probability $n$ items can be inserted using $O(n)$ insertions \cite{DRRT18}. For technical reasons we require $h_i(x)\neq h_j(x)$ for all $x$ and $i\neq j$. This can be achieved by defining $h_j(x)$ over the range $[m]\backslash \{h_{i}(x)\}_{i < j}$.
\else 
Typically the required table size is $m\approx1.6n$ for $\lambda=40$ bits of statistical security, see \cite{DRRT18}.
\fi